//https://leetcode.cn/problems/search-a-2d-matrix/submissions/503521218/?envType=study-plan-v2&envId=top-100-liked

#include <vector>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        if (rows < 1) {
            return false;
        };

        int column = matrix[0].size();
        if (column < 1) {
            return false;
        };

        // 寻找右上角的数值的位置
        int cur_row = 0;
        int cur_colun = column- 1;
        bool res = false;

        while (cur_row <= rows-1 && cur_colun >= 0) {

            int current_val = matrix[cur_row][cur_colun];

            if (current_val == target) {
                res=true;
                break;
            } else if (current_val > target) {
                --cur_colun;
            } else if (current_val < target) {
                ++cur_row;
            }
        }
        return res;
    }
};